package com.youshang.designpattern;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class q1n {
    public static void main(String[] args) throws InterruptedException {

        int m = Integer.parseInt("20"); // 网格大小
        int n = Integer.parseInt("20"); // 生成点数量
        int s = Integer.parseInt("100"); // 停顿时间

        List<CharacterN> CharacterNS = new ArrayList<>(); // 角色列表

        // 在地图外围生成角色
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            int x = random.nextInt(2 * m) - m;
            int y = random.nextInt(2 * m) - m;
            CharacterNS.add(new CharacterN(x, y, m));
        }

        long startTime = System.currentTimeMillis();

        // 模拟运行
        int totalMoves = 0;
        while (System.currentTimeMillis() - startTime < 10000) { // 运行10秒
            for (CharacterN CharacterN : CharacterNS) {
                if (!CharacterN.isAlive()) continue;

                CharacterN.move(CharacterNS);

                totalMoves++;
            }

            Thread.sleep(s);
        }

        System.out.println("Total moves: " + totalMoves);
    }
}

class CharacterN {
    private int x;
    private int y;
    private int m;
    private boolean alive;

    public CharacterN(int x, int y, int m) {
        this.x = x;
        this.y = y;
        this.m = m;
        this.alive = true;
    }

    public boolean isAlive() {
        return alive;
    }

    public void move(List<CharacterN> CharacterNS) {
        Random random = new Random();
        int targetX = random.nextInt(2 * m) - m;
        int targetY = random.nextInt(2 * m) - m;

        // 使用 Bresenham 算法计算直线路径
        List<int[]> path = calculatePath(x, y, targetX, targetY);

        // 执行移动
        for (int[] step : path) {
            int nextX = step[0];
            int nextY = step[1];

            // 检查是否与其他角色重叠
            boolean overlap = false;
            for (CharacterN other : CharacterNS) {
                if (other != this && other.isAlive() && other.getX() == nextX && other.getY() == nextY) {
                    overlap = true;
                    break;
                }
            }

            if (overlap) {
                alive = false;
                break;
            }

            x = nextX;
            y = nextY;

            // 到达目的地
            if (x == targetX && y == targetY) {
                break;
            }
        }
    }

    private List<int[]> calculatePath(int startX, int startY, int targetX, int targetY) {
        // 使用 Bresenham 算法计算直线路径
        List<int[]> path = new ArrayList<>();
        int dx = Math.abs(targetX - startX);
        int dy = Math.abs(targetY - startY);
        int sx = startX < targetX ? 1 : -1;
        int sy = startY < targetY ? 1 : -1;
        int err = dx - dy;

        while (true) {
            path.add(new int[]{startX, startY});

            if (startX == targetX && startY == targetY) {
                break;
            }

            int e2 = 2 * err;
            if (e2 > -dy) {
                err -= dy;
                startX += sx;
            }
            if (e2 < dx) {
                err += dx;
                startY += sy;
            }
        }

        return path;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}
